import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: AB16 实现二叉树先序，中序和后序遍历
 * <a href="https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=308&tqId=1008937&ru=/exam/company&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-05-21
 * Time: 23:34
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 解题思路:
     * 总体上没有太大难度, 主要就是清楚前中后序遍历,因为题目要求这个函数要返回一个二维数组,
     * 因此在便利的过程中使用 ArrayList 来临时存放遍历结果,之后存入res数组即可
     * @param root
     * @return
     */
    public int[][] threeOrders (TreeNode root) {
        //临时存放结果集
        ArrayList<Integer> pre = new ArrayList<>();
        ArrayList<Integer> mid = new ArrayList<>();
        ArrayList<Integer> post = new ArrayList<>();
        //分别进行前中后序遍历
        preOrder(root,pre);
        midOrder(root,mid);
        postOrder(root,post);
        //完善结果数组返回即可
        int[][] res = new int[3][pre.size()];
        for (int i = 0; i < pre.size(); i++) {
            res[0][i] = pre.get(i);
            res[1][i] = mid.get(i);
            res[2][i] = post.get(i);
        }
        return res;
    }

    private static void preOrder(TreeNode root, ArrayList<Integer> temp) {
        if (root == null) {
            return;
        }
        //根节点
        temp.add(root.val);
        //左子树
        preOrder(root.left,temp);
        //右子树
        preOrder(root.right,temp);
    }

    private static void midOrder(TreeNode root, ArrayList<Integer> temp) {
        if (root == null) {
            return;
        }
        //左子树
        midOrder(root.left,temp);
        //根节点
        temp.add(root.val);
        //右子树
        midOrder(root.right,temp);
    }

    private static void postOrder(TreeNode root, ArrayList<Integer> temp) {
        if (root == null) {
            return;
        }
        //左子树
        postOrder(root.left,temp);
        //右子树
        postOrder(root.right,temp);
        //根节点
        temp.add(root.val);
    }
}